package leetCode.q105;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.indexMap = new HashMap<Integer, Integer>();
        int n = preorder.length;
        for (int i = 0; i < n; i++) this.indexMap.put(inorder[i], i);
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    public TreeNode myBuildTree(int[] qian, int[] zhong, int qianl, int qianr, int zhongl, int zhongr) {
        if (qianl > qianr) return null;

        // 根节点值
        int rootValue = qian[qianl];
        int rootIndex = indexMap.get(rootValue);
        TreeNode gen = new TreeNode(rootValue);
        gen.left = myBuildTree(qian, zhong, qianl + 1, qianl + rootIndex - zhongl, zhongl, rootIndex - 1);
        gen.right = myBuildTree(qian, zhong, qianl + rootIndex - zhongl + 1, qianr, rootIndex + 1, zhongr);
        return gen;
    }
}
